//给定一个 N 叉树，返回其节点值的后序遍历。 
//
// 例如，给定一个 3叉树 : 
//
// 
//
// 
//
// 
//
// 返回其后序遍历: [5,6,3,2,4,1]. 
//
// 
//
// 说明: 递归法很简单，你可以使用迭代法完成此题吗? Related Topics 树 
// 👍 91 👎 0

package leetcode.editor.cn;

import common.bean.multiple.Node;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Java：N叉树的后序遍历
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P590_NAryTreePostorderTraversal {
    public static void main(String[] args) {
        Solution solution = new P590_NAryTreePostorderTraversal().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 迭代
     */
    class Solution {
        public List<Integer> postorder(Node root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Deque<Node> deque = new ArrayDeque<>();
            deque.push(root);
            while (!deque.isEmpty()) {
                // 看一下有没有子节点
                Node peek = deque.peek();
                if (peek.children != null) {
                    List<Node> children = peek.children;
                    for (int i = children.size() - 1; i >= 0; i--) {
                        deque.push(children.get(i));
                    }
                    // 将子节点集置为空
                    peek.children = null;
                } else {
                    // 拿出根节点
                    res.add(deque.pop().val);
                }
            }
            return res;
        }

    }
    ///**
    // * 递归
    // */
    //class Solution {
    //    public List<Integer> postorder(Node root) {
    //        List<Integer> res = new ArrayList<>();
    //        postorder(root, res);
    //        return res;
    //    }
    //
    //    private void postorder(Node root, List<Integer> list) {
    //        if (root == null) {
    //            return;
    //        }
    //        for (Node node : root.children) {
    //            postorder(node, list);
    //        }
    //        list.add(root.val);
    //    }
    //}
    //leetcode submit region end(Prohibit modification and deletion)

}
